package day28_35.day32;

import java.util.Scanner;

public class Main02 {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        long[] arr = new long[1000000];
        arr[0] = 1; arr[1] =2;
        for (int i = 2; i < arr.length; i++) {
            long cur = arr[i - 1] + arr[i - 2];
            arr[i] = cur % 1000000;
        }
        while (scn.hasNext()){
            String str = scn.next();
            String[] strArr = str.split("<br/>");
            for (int i = 0; i < strArr.length; i++) {
                int n = Integer.parseInt(strArr[i]);
                System.out.print(arr[n - 1]);
                if (i != strArr.length - 1) System.out.print("<br/>");
            }

        }
    }
}
